package 下一个更大元素II;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * createTime: 2025/5/25 0:10
 * description:
 *
 * @author AirMan
 */
public class Solution2 {
    public int[] nextGreaterElements(int[] nums) {
        // 很明显这是数组中寻找一个数字后面的最值问题 ==> 单调栈
        // 单调栈就是利用一个栈存放还未找到最值的索引，当单调栈是递增序列的时候，寻找的是右边的第一个最大值
        // 当单调栈是递减序列的时候，寻找的就是右边的第一个最小的值

        Deque<Integer> stack = new LinkedList<>();
        int[] result = new int[nums.length];
        Arrays.fill(result, -1);
        int size = nums.length;
        // 一共需要循环 2 * nums.length，达到"循环"的效果，以此来寻找循环中的"右边"第一个最大值
           for (int i = 0; i < 2 * size; i++) {
            while (!stack.isEmpty() && nums[i % size] > nums[stack.peek()]) {
                result[stack.peek()] = nums[i % size];
                // 将确定的索引出栈
                stack.pop();
            }
            // 如果当前元素还未确定，就入栈
            if (i < size) {
                stack.push(i % nums.length);
            }
        }
        return result;
    }
}
